package com.cat.gridChart;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/shortest-path-in-binary-matrix/description/
 * @create 2025/9/7 19:43
 * @since JDK17
 */

public class Solution13 {
    static int[][] q = new int[10010][2];
    public int shortestPathBinaryMatrix(int[][] grid) {
        int n = grid.length, t = 0, h = 0, ans = 0;
        if (n == 1) {
            return 0;
        }
        if (grid[0][0] != 0) {
            return -1;
        }
        boolean[][] vis = new boolean[n][n];
        q[t++] = new int[]{0, 0};
        vis[0][0] = true;
        while (h < t) {
            ans++;
            for (int end = t; h < end; h++) {
                var p = q[h];
                for (int i = Math.max(p[0] - 1, 0); i <= p[0] + 1 && i < n; i++) {
                    for (int j = Math.max(p[1] - 1, 0); j <= p[1] + 1 && j < n; j++) {
                        if ((i == p[0] && j == p[1]) || vis[i][j] || grid[i][j] != 0) {
                            continue;
                        }
                        q[t++] = new int[]{i, j};
                        vis[i][j] = true;
                    }
                }
            }
        }

        return -1;
    }
}
